package NO6_Tree;

/**
 * 2025-09-08
 * 力扣 - 114. 二叉树展开为链表
 * <p>
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 */
public class FlattenMain {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1,
                new TreeNode(2, new TreeNode(3), new TreeNode(4)),
                new TreeNode(5, new TreeNode(6), null));
        TreeNode.printTree(treeNode);
        TreeNode.printTreeSimple(treeNode);
        System.out.println("\n-------------");
        flatten(treeNode);
        TreeNode.printTreeSimple(treeNode);
    }

    public static void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.left);
        flatten(root.right);
        TreeNode left = root.left;
        TreeNode right = root.right;
        // 将左子树作为右子树
        root.left = null;
        root.right = left;
        // 将原先的右子树接到当前右子树的末端
        TreeNode p = root;
        while (p.right != null)
            p = p.right;
        p.right = right;
    }
}
